// https://www.lintcode.com/problem/first-missing-positive/description

class Solution {
public:
    /**
     * @param A: An array of integers
     * @return: An integer
     */
    int firstMissingPositive(vector<int> &A) {
        for (int i = 0; i < A.size(); ++i)
        {
            while (A[i] != i + 1 && A[i] >= 1 && A[i] <= A.size()) {
                if (A[A[i] - 1] == A[i]) {
                    break;
                }
                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        for (int i = 0; i < A.size(); ++i)
        {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.size() + 1;
    }
};